Accelerating Implicit Finite Difference Schemes Using a Hardware Optimized Tridiagonal Solver for FPGAs

摘要

We present a design and implementation of the Thomas algorithm optimized forhardware acceleration on an FPGA, the Thomas Core. The hardware-based algorithmcombined with the custom data flow and low level parallelism available in anFPGA reduces the overall complexity from 8N down to 5N serial arithmeticoperations, and almost halves the overall latency by parallelizing the twocostly divisions. Combining this with a data streaming interface, we reducememory overheads to 2 N-length vectors per N-tridiagonal system to be solved.The Thomas Core allows for multiple independent tridiagonal systems to becontinuously solved in parallel, providing an efficient and scalableaccelerator for many numerical computations. Finally we present applicationsfor derivatives pricing problems using implicit finite difference schemes on anFPGA accelerated system and we investigate the use and limitations offixed-point arithmetic in our algorithm.